package org.forever.util
{
	public class Graph_List implements Graph
	{
		/**容器：存放图中所有边*/
		public var E:List;
		/**容器：存放图中所有顶点*/
		public var V:List;
		
		public Graph_List() { E = new List_DLNode(); V = new List_DLNode(); }
		
		protected function  getE():List { return E; }
		protected function getV():List { return V; }
		
		public function vNumber():int { return V.getSize(); }
		public function eNumber():int { return E.getSize(); }
		
		public function vertices():Iterator { return V.elements(); }
		public function vPositions():Iterator { return V.positions(); }
		
		public function edges():Iterator { return E.elements(); }
		public function ePositions():Iterator { return E.positions(); }
		
		public function areAdjacent(u:Vertex, v:Vertex):Boolean
		{ return (null != edgeFromTo(u, v)); }
		
		public function edgeFromTo(u:Vertex, v:Vertex):Edge {
			for (var it:Iterator = u.getOutEdges(); it.hasNext();) {//逐一检查
				var e:Edge = it.getNext() as Edge;//以u为尾的每一条边e
				if (v == e.getVPosInV(1).getElem())//若e是(u, v)，则
					return e;//返回该边
			}
			return null;//若不存在这样的(u, v)，则返回null
		}
		
		public function removeV(v:Vertex):Vertex
		{
			while (0 < v.outDeg()){//将以v为尾的所有边
				var vl:Vertex_List = v as Vertex_List;
				removeE(((v as Vertex_List).outEdges.first()).getElem() as Edge);//逐一删除
			}
			while (0 < v.inDeg())//将以v为头的所有边
				removeE(((v as Vertex_List).inEdges.first()).getElem() as Edge);//逐一删除
			return V.remove(v.getVPosInV()) as Vertex;//在顶点表中删除v
		}
		
		public function removeE(e:Edge):Edge
		{
			(e.getVPosInV(0).getElem() as Vertex_List).outEdges.remove(e.getEPosInI(0));//从起点的出边表中删除e
			(e.getVPosInV(1).getElem() as Vertex_List).inEdges.remove(e.getEPosInI(1));//从终点的入边表中删除e
			return E.remove(e.getEPosInE()) as Edge;//从边表中删除e
		}
		
		public function insertV(v:Vertex):Position
		{
			return V.insertLast(v);
		}
		
		public function insertE(e:Edge):Position
		{
			return E.insertLast(e);
		}
		
	}
}